The present invention relates to disk systems for use in digital computers. In particular this invention is an apparatus and method for improving the response performance of a disk drive system. This response improvement is achieved by the optimized placement of disk sectors associated with a directory, and File Allocation Tables, on the disk drive.
Personal computers have gained widespread acceptance today and millions of personal computers are in use in businesses and homes. While many operating systems are available for these computers, the Microsoft Disk Operating System (MS-DOS) is a leading operating system currently in use. MS-DOS is also marketed under other brand names. For example, the IBM Personal Computer Disk Operating System (PC-DOS) is, with minor exceptions, a relabeled MS-DOS. The operation of the MS-DOS/PC-DOS (DOS) is well understood by those skilled in the art and the technical features of the operating system are documented in the IBM "Disk Operating System Technical Reference", version 5.00.
A hard (fixed) disk typically has multiple disk platters. Each platter is coated with magnetic material and typically one magnetic disk head per platter surface is provided to record data onto the platter surface. Each of the disk heads are mounted on a common arm which is moved in discrete increments to locate the heads on a particular disk cylinder. A cylinder is comprised of all the disk tracks that line up under a head. For example if a disk has two platters and therefore four disk heads, there would be four tracks that make up a cylinder. Each track is divided into sectors with each sector storing multiple bytes of data. The number of sectors is determined when the disk is formatted by a format program.
Allocation of disk space for a file (in the disk data area) is done only when needed. That is, the data space is not preallocated. The space is allocated one cluster (unit of allocation) at a time where a cluster is one or more consecutive disk sectors. The clusters for a file are "chained" together, and kept track of, by entries in a File Allocation Table (FAT).
The clusters are arranged on the disk to minimize the disk head movement. All of the space on a track (or cylinder) is allocated before moving on to the next track. This is accomplished by using the sequential sectors on the lowest-numbered head, then all the sectors on the next head, and so on until all sectors on all heads of the cylinder are used. Then, the next sector to be used will be sector 1 on head 0 of the next cylinder.
For a hard (fixed) disk, the size of the FAT and directory are determined when a disk format program initializes the disk, and are based on the size of the DOS partition. To locate all of the data that is associated with a particular file stored on a hard disk, the starting cluster of the file is obtained from the directory entry, then the FAT table is referenced to locate the next cluster associated with the file. The FAT table is a linked list of cluster pointers such that each 16-bit FAT entry for a file points to the next sequential cluster used for that file. The last entry for a file in the FAT has a number which indicates that no more clusters follow. This number can be from FFF8 to FFFF (base 16) inclusive. The size of a cluster is defined when the disk is formatted and can range from 1 to 128 sectors. Each sector of a FAT can point to 256, 512, . . . , or 32768 sectors depending of the number of sectors in a cluster. The number of sectors that a FAT sector can point to is called a "track group". For redundancy reasons, two identical FATs are provided on the disk.
FIG. 1A shows a directory entry 2 consisting of 32 bytes of data. The name of the file and its extension are stored in the first 11 bytes (4) of the directory entry 2 and a file attribute byte 6 is provided. By definition, 10 bytes 8 are reserved for future use and 2 bytes are provided to store time 10 and date 12 information. Cluster bytes 14 point to the first cluster of sectors used to store the file information and the bytes 14 point to the first entry of the FAT table 16 associated with the file. The last 4 bytes 18 of the directory entry 2 are used to store the size of the file.
A 16 byte section of a FAT table 20 is depicted. The first 4 bytes 21 store system information. A two-byte pair, bytes 4 and 5 (16), are the beginning bytes of the FAT 20 used to track file information. The first cluster for data space on all disks is cluster "02". Therefore, bytes 4 and 5 (16) are associated with the first cluster of disk sectors "02" used to store file information. FAT bytes 6 and 7 (22) are associated with cluster 03 . . . and bytes 14 and 15 (24) are associated with cluster 07.
This example illustrates how sectors associated with a file referenced in the directory are located. The cluster information bytes 14 in the directory 2 point to cluster number "02". The sectors in cluster "02" not shown, contain the first part of the data for the referenced file. Next the FAT table is referenced to see if additional clusters are used to store the file information. FAT bytes 4 and 5 (16) were pointed to by the directory entry 14 and the information stored in bytes 4 and 5 (16) point to the next cluster used for the file. Here the next cluster is "05". So, cluster "05" contains the next part of the data for the referenced file. FAT bytes 10 and 11 (26) contain an end-of-file number "FFFF" indicating there are no more clusters associated with the referenced file. All of the information associated with the referenced file was contained in clusters "02" and "05" on the disk.
FIG. 1B shows a schematic view of the organization of the two FATs and the directory on a simple disk. The disk 102 has an outside track 104 which contains the first FAT information. The next inner track 106 contains the second FAT information. The next sequential track 108, toward the center of the disk, contains the directory information. The outer most (track 0) of the disk, not shown, is reserved for the storage of the computer boot up instructions.
FIG. 2 shows a graphical view of the storage area of the disk in FIG. 1. The information for the FATs 104 and 106 is stored in the first and second tracks shown and the information for the directory 108 is stored in the third track shown. The remaining storage area of the disk 202 is available for storing file information. Beginning with track 1, sector 1, the operating system uses up to 128 contiguous sectors for the first copy of the FAT 1 (104). The operating system then allocates an additional, duplicate contiguous space for the FAT 2 (106). After both FATs have been allocated, the operating system allocates the next 32 contiguous sectors for the root directory 108.
The simple disk illustrated in FIG. 1 and FIG. 2 has a single recording surface and would only have a single recording head. Therefore, a track would be equivalent to a cylinder. Also for simplicity, the directory 108 and the two FATs 104 and 106 are assumed to occupy a single track each. The disk is organized into logical blocks with each block representing a sector of the disk. If the disk was organized to have 5000 sectors total, then the disk would have 5000 logical blocks. In prior art disk drives, the logical blocks map linearly and sequentially to the physical track-sector locations.
FIG. 3 illustrates the process required to read a file from a disk. Since the disk is in constant use, on average, the heads of the disk can be considered to be located about midway 302 relative to the platter surface. The read process is as follows:
Step 1: Seek (move the heads) from the current position to read the file information in the directory. PA1 Step 2: Seek and read the file information in the FAT 1. PA1 Step 3: Seek and read the file data stored in the cluster of sectors in the data area of the disk. Repeat Step 2 if the file data are contained in an additional cluster. PA1 Step 1: Seek and read the directory to get FAT information. PA1 Step 2: Seek and read the information in the FAT 1 to find the location of an unallocated cluster. PA1 Step 3: Seek and write one cluster of file data starting at the first sector of the cluster pointed to by the FAT 1 pointer. PA1 Step 4: Seek and write updated information in the FAT 1. PA1 Step 5: Seek and write updated information in the FAT 2 to mirror the data in FAT 1. PA1 Step 6: Seek and read FAT 1 to get an additional cluster if required. If more than one cluster was required to store the file information, then repeat the process starting at step 3. PA1 Step 7: Seek and write updated information into the directory such as the file name and the size of the file.
The time the heads require to seek (seek time) is related to the distance the heads are required to move. Longer seeks therefore take longer to perform. Also, in normal use, the file information is read only from the FAT 1. As the disk is rotating, there is a latency (rotational latency) incurred between the time the head is located above the correct track and the time the proper sector is positioned under the head. On average, this latency is one-half the time it takes the platter to make one revolution. The ability to read data quickly is negatively impacted by the combined seek time and rotational latency.
FIG. 4 illustrates the process required to write data to a disk file. As in the example above, the heads are assumed to be in the middle of the disk where they were left from a previous process.
The write process is as follows:
The write process requires many more seeks than the read process and therefore incurs more overhead in terms of seek times and rotational latencies. This overhead increases the overall response time of the disk drive system.
While disk drives have been improved to decrease the head seek time, the seek time and rotational latency still contribute significantly to the time it takes a disk to perform a read or write. What is needed in the industry is a disk drive with greatly reduced seek time and rotational latency.